//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_LOCKFREELIST_H
#define HYDRA_LOCKFREELIST_H 1

#include "hydra/allocators/DelayedFreeAllocator.h"
#include "hydra/atomic/AtomicMarkablePtr.h"

namespace Hydra
{
	template<typename T, typename Allocator=DelayedFreeAllocator>
	class LockFreeList
	{
	private:
		struct Node
		{
			T m_item;
			AtomicMarkablePtr<Node> m_next;
		};

	public:
        static_assert(!Allocator::kAbaVulnerable, "Allocator must not be vulnerable to the ABA problem");

		class ConstIterator;
		/**
		 * Note that the Iterator::next function can fail, resetting the Iterator to the front of the list. This is because the
		 * iterator must remove marked nodes from the list as it traverses, which can fail if multiple threads are traversing simultaneously.
		 * Use ConstIterator if there is no need to make modifications to the list, it does not removed marked nodes and cannot fail.
		 */
		class Iterator
		{
			friend class LockFreeList;
		public:
			explicit Iterator() { }
			explicit Iterator(LockFreeList& list) : m_list(&list)
			{
				toFront();
			}
			explicit Iterator(LockFreeList& list, Node* pred) : m_list(&list)
			{
				setPred(pred);
			}
			/**
			 * Gets the item currently pointed to by the Iterator and steps the Iterator to the next item in the list.
			 * Returns true on success if an item was returned. Returns false on failure, this can occur due to the
			 * failure of marked node removal. In this case the iterator will be reset to the start of the list.
			 */
			bool next(T& item)
			{
				assert(hasNext());

				//m_curr could actually be marked now... that's ok, our linearization point was on the previous call
				// to next(), m_curr was verified to be unmarked then.
				item = m_curr->m_item;

				//step to the next node, using the m_succ which was read from the unmarked node
				m_pred = m_curr;
				m_curr = m_succ;

				//remove marked nodes, return true if successful
				if( cleanMarkedNodes() )
					return true;

				//The marked node removal failed, the iterator is now invalid and useless.
				//We reset the iterator to the start of the list and return false to let the caller know the iterator
				// has been reset. We could let the user decide if they want to reset the iterator, but there doesn't
				// seem to be any useful algorithm which would not need the iterator to be reset, and leaving the
				// iterator in an invalid state would be dangerous, so we'll reset it here.
				toFront();
				return false;
			}
			///Returns the item currently pointed to by the Iterator, without stepping forward
			const T peekNext()
			{
				assert(hasNext());
				return m_curr->m_item;
			}
			///Returns false if the Iterator is at the end of the list
			bool hasNext()
			{
				return (m_curr->m_next.getPtr() != NULL);
			}
			void toFront()
			{
				setPred(&m_list->m_head);
			}
			Iterator& operator=(const Iterator& rhs)
			{
				m_list = rhs.m_list;
				m_pred = rhs.m_pred;
				m_curr = rhs.m_curr;
				m_succ = rhs.m_succ;
				return *this;
			}

		private:
			void setPred(Node* pred)
			{
				//remove marked nodes, repeat until successful and we have a valid m_curr
				while( true )
				{
					m_pred = pred;
					m_curr = m_pred->m_next.getPtr();
					if( cleanMarkedNodes() )
						break;
				}
			}
			bool cleanMarkedNodes()
			{
				//remove the marked nodes, this can fail and reset the iterator if other iterators are concurrently making changes
				bool mark;
				m_succ = m_curr->m_next.get(mark);
				while( mark )
				{
					if( !m_pred->m_next.compareAndSwap(m_succ, false, m_curr, false) )
					{
						//removal failed, note that the iterator is now invalid and should be reset
						return false;
					}
					//removal was successful, so release the node and step to the next node
					m_list->freeNode(m_curr);
					m_curr = m_succ;
					m_succ = m_curr->m_next.get(mark);
				}
				return true;
			}

			LockFreeList* m_list;
			Node* m_pred;
			Node* m_curr;
			Node* m_succ;
		};

		/**
		 * A simpler, faster iterator which can traverse the list but cannot make modifications. It does not remove marked nodes,
		 * so unlike the Iterator the traversal cannot fail. It will skip marked nodes while traversing.
		 */
		class ConstIterator
		{
			friend class Iterator;
		public:
			ConstIterator(LockFreeList& list) : m_list(&list)
			{
				toFront();
			}
			explicit ConstIterator(Iterator& iter) : m_list(iter.m_list)
			{
				m_curr = iter.m_curr;
				skipMarkedNodes();
			}
			const T next()
			{
				assert(hasNext());
				T item = m_curr->m_item;

				//step to next node, repeat if node is marked
				bool mark;
				Node* succ = m_curr->m_next.getPtr();
				do 
				{
					m_curr = succ;
					succ = m_curr->m_next.get(mark);
				} while (mark && succ);

				return item;
			}
			///Returns the item currently pointed to by the Iterator, without stepping forward
			const T peekNext()
			{
				assert(hasNext());
				return m_curr->m_item;
			}
			///Returns false if the Iterator is at the end of the list
			bool hasNext()
			{
				return (m_curr->m_next.getPtr() != NULL);
			}
			void toFront()
			{
				m_curr = m_list->m_head.m_next.getPtr();
				//skip any marked nodes at the start of the list
				skipMarkedNodes();
			}
			Iterator getNextIterator() const
			{
				return Iterator(*m_list, m_curr);
			}
		private:
			void skipMarkedNodes()
			{
				bool mark;
				Node* succ = m_curr->m_next.get(mark);
				while( mark )
				{
					m_curr = succ;
					succ = m_curr->m_next.get(mark);
				}
			}
			LockFreeList* m_list;
			Node* m_curr;
		};

		LockFreeList()
		{
			m_head.m_next.set(&m_alloc.m_tail, false);
			m_alloc.m_tail.m_next.set(NULL, false);
		}

		~LockFreeList()
		{
			//free all nodes
			Node* node = m_head.m_next.getPtr();
			Node* nextNode = node->m_next.getPtr();
			while( nextNode )
			{
				freeNode(node);
				node = nextNode;
				nextNode = node->m_next.getPtr();
			}
		}

		void pushFront(const T& item)
		{
			Node* newNode = allocNode();
			newNode->m_item = item;

			//don't need to remove marked nodes here, as head node can never be marked
			while( true )
			{
				Node* nextNode = m_head.m_next.getPtr();
				newNode->m_next.set(nextNode, false);
				if( m_head.m_next.compareAndSwap(newNode, false, nextNode, false) )
					return;
			}
		}

		bool front(T& item)
		{
			//use the ConstIterator since it will skip any marked nodes at the start of the list
			ConstIterator iter(*this);
			if( iter.hasNext() )
			{
				item = iter.peekNext();
				return true;
			}
			return false;
		}

		bool popFront(T& item)
		{
			while( true )
			{
				Iterator iter(*this);
				if( !iter.hasNext() )
					break;
				item = iter.peekNext();
				bool isReset;
				if( remove(iter, isReset) )
					return true;
			}
			return false;
		}

		/**
		 * Inserts the new item before the item currently pointed to by the Iterator. If successful the
		 * iterator will be pointing to the new item after this function.
		 */
		bool insert(Iterator& iter, const T& item)
		{
			Node* newNode = allocNode();
			newNode->m_item = item;

			newNode->m_next.set(iter.m_curr, false);
			if( iter.m_pred->m_next.compareAndSwap(newNode, false, iter.m_curr, false) )
			{
				iter.m_succ = iter.m_curr;
				iter.m_curr = newNode;
				return true;
			}

			freeNode(newNode);
			return false;
		}

		bool contains(const T& item)
		{
			ConstIterator iter(*this);
			while( iter.hasNext() )
			{
				T cmpItem = iter.next();
				if( cmpItem == item )
					return true;
			}
			return false;
		}

		/**
		 * Removes the item pointed to by iter, after a successful removal the Iterator will be pointing to the next item in the list,
		 * unless isReset is true in which case the iterator has been reset to the start of the list. Note that the removal was still
		 * successful even though the iterator has been reset. Returns false if the removal failed due to concurrent modification of
		 * the list, the iterator will be unchanged if removal failed.
		 */
		bool remove(Iterator& iter, bool& isReset)
		{
			isReset = false;
			if( iter.m_curr->m_next.compareAndSwap(iter.m_succ, true, iter.m_succ, false) )
			{
				//removal was successful, attempt to move iterator to next item
				if( !iter.cleanMarkedNodes() )
				{
					//failure moving iterator to next item, reset the iterator and notify the user
					iter.toFront();
					isReset = true;
				}
				//item has been successfully removed, even if the iterator has been invalidated and reset, so return true
				return true;
			}
			//item has not been removed. Don't need to reset iterator, up to the user to decide if they restart
			return false;
		}

		///Removes the first occurrence of item from the list, uses operator== to compare.
		bool remove(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				if( iter.peekNext() == item )
				{
					if( iter.m_curr->m_next.compareAndSwap(iter.m_succ, true, iter.m_succ, false) )
					{
						//mark successful, try and remove the node from the list too, we don't care if this fails as the iterators will clean it up eventually
						if( iter.m_pred->m_next.compareAndSwap(iter.m_succ, false, iter.m_curr, false) )
							freeNode(iter.m_curr);
						return true;
					}
					//marking failed, we must reset the iterator to the start of the list to remove this item
					iter.toFront();
				}
				else
				{
					T dummy;
					iter.next(dummy);	//if this fails the iterator will be reset, so the search will be restarted
				}
			}
			return false;
		}

		///Removes all occurrences of item from the list, uses operator== to compare.
		void removeAll(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				if( iter.peekNext() == item )
				{
					//if removal fails, reset the iterator. A successful removal may also reset the iterator
					bool isReset;
					if( !remove(iter, isReset) )
						iter.toFront();
				}
				else
				{
					T dummy;
					iter.next(dummy);	//if this fails the iterator will be reset, so the search will be restarted
				}
			}
		}

		bool isEmpty()
		{
			//use the ConstIterator since it will skip marked nodes, and if all nodes are marked the list is considered empty
			ConstIterator iter(*this);
			return !iter.hasNext();
		}

		///Removes all items from the list, note that this is not necessarily fast as each item must be removed individually
		void clear()
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				//if removal fails, reset the iterator. A successful removal may also reset the iterator
				bool isReset;
				if( !remove(iter, isReset) )
					iter.toFront();
			}
		}

        static_assert(!Allocator::kAbaVulnerable, "Allocator must not be vulnerable to the ABA problem");

	private:
		Node* allocNode()
		{
			Node* node = reinterpret_cast<Node*>(m_alloc.alloc(sizeof(Node)));
			new(node) Node;
			return node;
		}
		void freeNode(Node* node)
		{
			node->~Node();
			m_alloc.free(node);
		}

		struct AllocAndTail : public Allocator
		{
			Node m_tail;
		};
		Node m_head;
		AllocAndTail m_alloc;
	};
}

#endif
